package hero.mps.sort;

import java.util.Arrays;

public class HeatOperator {

    /**
     * 上调整函数，用于将指定的元素向上调整，保证堆的性质。
     *
     * @param array 需要进行调整的数组
     */
    public static void upAdjust(int array[]) {
        // 最后一个非叶子节点的索引
        int childIndex = array.length - 1;
        // 父节点的索引
        int parentIndex = (childIndex - 1) / 2;
        // 当前要调整的值
        int temp = array[childIndex];
        // 当当前节点不是根节点且当前节点的值小于父节点的值时，进行循环
        while (childIndex > 0 && temp < array[parentIndex]){
            // 将父节点的值赋给当前节点
            array[childIndex] = array[parentIndex];
            // 更新当前节点的索引为父节点的索引
            childIndex = parentIndex;
            // 更新父节点的索引
            parentIndex = (childIndex - 1) / 2;
        }
        // 将temp值放到最终位置
        array[parentIndex] = temp;
    }


    /**
     * 从给定的父节点开始向下调整堆，保证堆的性质。
     *
     * @param array       待调整的数组
     * @param parentIndex 父节点在数组中的索引
     * @param length      数组的长度
     */
    public static void downSmallAdjust(int array[], int parentIndex, int length) {
        // 暂存父节点的值
        int temp = array[parentIndex];
        // 子节点索引初始化为父节点的左子节点
        int childIndex = 2 * parentIndex + 1;
        // 当子节点索引小于数组长度时循环
        while (childIndex < length) {
            // 如果右子节点存在且右子节点小于左子节点
            if (childIndex + 1 < length && array[childIndex] > array[childIndex + 1]) {
                // 子节点索引指向右子节点
                childIndex++;
            }
            // 如果父节点值小于等于子节点值，则跳出循环
            if (temp <= array[childIndex]) break;
            // 将子节点的值赋给父节点
            array[parentIndex] = array[childIndex];
            // 更新父节点索引为当前子节点索引
            parentIndex = childIndex;
            // 更新子节点索引为新的父节点的左子节点
            childIndex = 2 * parentIndex + 1;
        }
        // 将暂存的父节点值放到最终位置
        array[parentIndex] = temp;
    }


    /**
     * 构建堆
     *
     * @param array 需要构建成堆的数组
     */
    public static void buildHeap(int array[]) {
        // 从最后一个非叶子节点开始向前遍历
        for (int i = array.length / 2 - 1; i >= 0; i--) {
            // 调用downAdjust函数进行向下调整
            // 使得以当前节点为根的子树满足堆的性质
            downSmallAdjust(array, i, array.length);
        }
    }

    /**
     * 下调大堆函数
     *
     * @param array       待调整的数组
     * @param parentIndex 父节点在数组中的索引
     * @param length      数组的长度
     */
    public static void downLargeAdjust(int array[], int parentIndex, int length) {
        // 暂存父节点的值
        int temp = array[parentIndex];
        // 子节点索引初始化为父节点的左子节点
        int childIndex = 2 * parentIndex + 1;
        // 当子节点索引小于数组长度时循环
        while (childIndex < length) {
            // 如果右子节点存在且右子节点大于左子节点
            if (childIndex + 1 < length && array[childIndex] < array[childIndex + 1]) {
                // 子节点索引指向右子节点
                childIndex++;
            }
            // 如果父节点值大于等于子节点值，则跳出循环
            if (temp >= array[childIndex]) break;
            // 将子节点的值赋给父节点
            array[parentIndex] = array[childIndex];
            // 更新父节点索引为当前子节点索引
            parentIndex = childIndex;
            // 更新子节点索引为新的父节点的左子节点
            childIndex = 2 * parentIndex + 1;
        }
        // 将暂存的父节点值放到最终位置
        array[parentIndex] = temp;
    }

    public static void heapSort(int array[]) {
        for (int i = (array.length - 1) / 2; i >= 0; i--) {
            downLargeAdjust(array, i, array.length);
        }
        for (int i = array.length - 1; i > 0; i--) {
            int temp = array[0];
            array[0] = array[i];
            array[i] = temp;
            downLargeAdjust(array, 0, i);
        }
    }

    public static void main(String[] args) {
        int array[] = {1, 5, 8, 9, 6, 7};
        upAdjust(array);
        System.out.println(Arrays.toString(array));
        array = new int[]{1, 5, 8, 9, 6, 7};
        downSmallAdjust(array, 0, array.length);
        System.out.println(Arrays.toString(array));
        heapSort(array);
        System.out.println(Arrays.toString(array));
    }

}
